package com.zhugang.week13.sorting;

/**
 * @program algorithms
 * @description: quickSort2
 * @author: chanzhugang
 * @create: 2022/10/01 00:15
 */
public class QuickSort2 implements IMutableSorter {

    /**
     * 快排
     *
     * @param A
     */
    @Override
    public void sort(int[] A) {
        quickSort(A, 0, A.length);
    }

    private void quickSort(int[] A, int l, int r) {
        if (r - l <= 1) {
            return;
        }
        // 分区函数： 随机找一个数(找第一个数)，将数据分成两半，q是那个分的数据下标
        int q = partition(A, l, r);
        quickSort(A, l, q);
        quickSort(A, q + 1, r);
    }

    private int partition(int[] A, int l, int r) {
        // x | <x的值  ｜ 中间不确定的值  ｜ >x的值
        int x = A[l];
        // 前后双指针往中间压缩
        int i = l + 1;
        int j = r;
        while (i != j) {
            if (A[i] < x) {
                i++;
            } else {
                // 大于val的值交换到后面
                swap(A, i, --j);
            }
        }
        // i == j, 交换 x值的位置
        swap(A, i - 1, l);
        return i - 1;
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}